/*
 *                  Corsen development code
 *
 * This code may be freely distributed and modified under the
 * terms of the GNU General Public Licence version 2 or later. This
 * should be distributed with the code. If you do not have a copy,
 * see:
 *
 *      http://www.gnu.org/licenses/gpl-2.0.txt
 *
 * Copyright for this code is held jointly by the microarray platform
 * of the École Normale Supérieure and the individual authors.
 * These should be listed in @author doc comments.
 *
 * For more information on the Corsen project and its aims,
 * or to join the Corsen google group, visit the home page
 * at:
 *
 *      http://transcriptome.ens.fr/corsen
 *
 */

package fr.ens.transcriptome.corsen.gui.marchingcubes;

import java.util.ArrayList;
import java.util.List;

import javax.vecmath.Point3f;

import fr.ens.transcriptome.corsen.model.BitMapParticle3D;
import fr.ens.transcriptome.corsen.model.Particle3D;

/**
 * This class implements the marching cube algorithm. This code came from ImageJ
 * 3D Viewer by Benjamin Schmid
 * http://132.187.25.13/home/?category=Download&page=Viewer3D 
 * http://132.187.25.13/ImageJ/ImageJ_3D_Viewer.jar 
 * @author Benjamin Schmid
 * @author Laurent Jourdren
 */
public final class MCCube {

  // default size of the cubes
  public static final float SIZE = 1.0f;

  // vertexes
  private Point3f[] v;

  // interpolated values
  private Point3f[] e;

  /**
   * constructor of a MCCube object _________ 0______x /v0 v1/| /| /________/ | / |
   * |v3 v2| /v5 y/ |z |________|/ v7 v6
   */
  private MCCube(int x, int y, int z) {
    this.v = new Point3f[8];

    v[0] = new Point3f(x, y, z);
    v[1] = new Point3f(x + SIZE, y, z);
    v[2] = new Point3f(x + SIZE, y - SIZE, z);
    v[3] = new Point3f(x, y - SIZE, z);
    v[4] = new Point3f(x, y, z + SIZE);
    v[5] = new Point3f(x + SIZE, y, z + SIZE);
    v[6] = new Point3f(x + SIZE, y - SIZE, z + SIZE);
    v[7] = new Point3f(x, y - SIZE, z + SIZE);
    this.e = new Point3f[12];
    computeEdges();
  }

  /**
   * computes the case number of the cube
   * @return the number of the case corresponding to the cube
   */
  private int caseNumber() {

    int caseNumber = 0;
    for (int index = -1; ++index < v.length; caseNumber +=
        (intensity(v[index]) - threshold > 0) ? 1 << index : 0)
      ;

    return caseNumber;
  }

  /**
   * computes the interpolated point along a specified whose intensity equals
   * the reference value
   * @param v1 first extremity of the edge
   * @param v2 second extremity of the edge
   * @return the point on the edge where intensity equals the isovalue; null is
   *         interpolated point is beyond edge boundaries
   */
  private static final Point3f computeEdge(final Point3f v1, final Point3f v2) {

    float t =
        (threshold - intensity(v1)) / (float) (intensity(v2) - intensity(v1));

    if (t >= 0 && t <= 1) {

      Point3f vDir = new Point3f(v2);
      vDir.sub(v1);
      vDir.scale(t);
      vDir.add(v1);
      return vDir;
    }
    return null;
  }

  /**
   * computes interpolated values along each edge of the cube (null if
   * interpolated value doesn't belong to the edge)
   */
  private void computeEdges() {

    this.e[0] = computeEdge(v[0], v[1]);
    this.e[1] = computeEdge(v[1], v[2]);
    this.e[2] = computeEdge(v[2], v[3]);
    this.e[3] = computeEdge(v[3], v[0]);

    this.e[4] = computeEdge(v[4], v[5]);
    this.e[5] = computeEdge(v[5], v[6]);
    this.e[6] = computeEdge(v[6], v[7]);
    this.e[7] = computeEdge(v[7], v[4]);

    this.e[8] = computeEdge(v[0], v[4]);
    this.e[9] = computeEdge(v[1], v[5]);
    this.e[10] = computeEdge(v[3], v[7]);
    this.e[11] = computeEdge(v[2], v[6]);
  }

  private void getTriangles(List<Point3f> list) {

    // address in the table

    int offset = this.caseNumber() * 15;
    for (int index = 0; index < 5; index++) {

      // if there's a triangle
      if (faces[offset] != -1) {

        // pick up vertexes of the current triangle
        list.add(this.e[faces[offset + 0]]);
        list.add(this.e[faces[offset + 1]]);
        list.add(this.e[faces[offset + 2]]);
      }
      offset += 3;
    }
  }

  private static BitMapParticle3D bitmap;
  private static final int threshold = 0;

  private static int intensity(final Point3f p) {

    final int x = (int) p.x;
    final int y = (int) p.y;
    final int z = (int) p.z;

    return bitmap.getBitMapIntensity(x, y, z);
  }

  public static final List<Point3f> getTriangles(Particle3D particle) {

    final List<Point3f> tri = new ArrayList<Point3f>();

    bitmap = particle.getBitMapParticle();

    final int w = bitmap.getXLen();
    final int h = bitmap.getYLen();
    final int d = bitmap.getZLen();

    final int size = (int) SIZE;

    for (int z = 0; z < d - 1; z += size)
      for (int x = 0; x < w - size; x += size)
        for (int y = size; y < h; y += size)
          new MCCube(x, y, z).getTriangles(tri);

    // convert pixel coordinates
    final float pwidth = bitmap.getPixelWidth();
    final float pheight = bitmap.getPixelHeight();
    final float pdepth = bitmap.getPixelDepth();
    
    List<Point3f> ret = new ArrayList<Point3f>(tri.size());
    for (int i = 0; i < tri.size(); i++) {

      final Point3f p = tri.get(i);
       ret.add(new Point3f(p.x * pwidth, p.y * pheight, p.z * pdepth));
    }

    return ret;
  }

  // triangles to be drawn in each case
  private static int faces[] =
      {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, -1,
          -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 9, -1, -1, -1, -1,
          -1, -1, -1, -1, -1, -1, -1, -1, 1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1,
          -1, -1, -1, -1, 1, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
          -1, 0, 8, 3, 1, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 2, 11,
          0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 8, 3, 2, 11, 8, 11,
          9, 8, -1, -1, -1, -1, -1, -1, 3, 10, 2, -1, -1, -1, -1, -1, -1, -1,
          -1, -1, -1, -1, -1, 0, 10, 2, 8, 10, 0, -1, -1, -1, -1, -1, -1, -1,
          -1, -1, 1, 9, 0, 2, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 10,
          2, 1, 9, 10, 9, 8, 10, -1, -1, -1, -1, -1, -1, 3, 11, 1, 10, 11, 3,
          -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 11, 1, 0, 8, 11, 8, 10, 11,
          -1, -1, -1, -1, -1, -1, 3, 9, 0, 3, 10, 9, 10, 11, 9, -1, -1, -1, -1,
          -1, -1, 9, 8, 11, 11, 8, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4,
          7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 3, 0, 7, 3,
          4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 1, 9, 8, 4, 7, -1, -1, -1,
          -1, -1, -1, -1, -1, -1, 4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1,
          -1, -1, 1, 2, 11, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 4,
          7, 3, 0, 4, 1, 2, 11, -1, -1, -1, -1, -1, -1, 9, 2, 11, 9, 0, 2, 8,
          4, 7, -1, -1, -1, -1, -1, -1, 2, 11, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4,
          -1, -1, -1, 8, 4, 7, 3, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1,
          10, 4, 7, 10, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, 9, 0, 1, 8, 4,
          7, 2, 3, 10, -1, -1, -1, -1, -1, -1, 4, 7, 10, 9, 4, 10, 9, 10, 2, 9,
          2, 1, -1, -1, -1, 3, 11, 1, 3, 10, 11, 7, 8, 4, -1, -1, -1, -1, -1,
          -1, 1, 10, 11, 1, 4, 10, 1, 0, 4, 7, 10, 4, -1, -1, -1, 4, 7, 8, 9,
          0, 10, 9, 10, 11, 10, 0, 3, -1, -1, -1, 4, 7, 10, 4, 10, 9, 9, 10,
          11, -1, -1, -1, -1, -1, -1, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1,
          -1, -1, -1, -1, 9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1,
          0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, 5, 4, 8, 3,
          5, 3, 1, 5, -1, -1, -1, -1, -1, -1, 1, 2, 11, 9, 5, 4, -1, -1, -1,
          -1, -1, -1, -1, -1, -1, 3, 0, 8, 1, 2, 11, 4, 9, 5, -1, -1, -1, -1,
          -1, -1, 5, 2, 11, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, 2, 11, 5,
          3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, 9, 5, 4, 2, 3, 10, -1, -1, -1,
          -1, -1, -1, -1, -1, -1, 0, 10, 2, 0, 8, 10, 4, 9, 5, -1, -1, -1, -1,
          -1, -1, 0, 5, 4, 0, 1, 5, 2, 3, 10, -1, -1, -1, -1, -1, -1, 2, 1, 5,
          2, 5, 8, 2, 8, 10, 4, 8, 5, -1, -1, -1, 11, 3, 10, 11, 1, 3, 9, 5, 4,
          -1, -1, -1, -1, -1, -1, 4, 9, 5, 0, 8, 1, 8, 11, 1, 8, 10, 11, -1,
          -1, -1, 5, 4, 0, 5, 0, 10, 5, 10, 11, 10, 0, 3, -1, -1, -1, 5, 4, 8,
          5, 8, 11, 11, 8, 10, -1, -1, -1, -1, -1, -1, 9, 7, 8, 5, 7, 9, -1,
          -1, -1, -1, -1, -1, -1, -1, -1, 9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1,
          -1, -1, -1, -1, 0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, 1,
          5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 7, 8, 9, 5, 7,
          11, 1, 2, -1, -1, -1, -1, -1, -1, 11, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7,
          3, -1, -1, -1, 8, 0, 2, 8, 2, 5, 8, 5, 7, 11, 5, 2, -1, -1, -1, 2,
          11, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, 7, 9, 5, 7, 8, 9, 3,
          10, 2, -1, -1, -1, -1, -1, -1, 9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 10,
          -1, -1, -1, 2, 3, 10, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, 10, 2,
          1, 10, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, 9, 5, 8, 8, 5, 7, 11,
          1, 3, 11, 3, 10, -1, -1, -1, 5, 7, 0, 5, 0, 9, 7, 10, 0, 1, 0, 11,
          10, 11, 0, 10, 11, 0, 10, 0, 3, 11, 5, 0, 8, 0, 7, 5, 7, 0, 10, 11,
          5, 7, 10, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 11, 6, 5, -1, -1,
          -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 5, 11, 6, -1, -1,
          -1, -1, -1, -1, -1, -1, -1, 9, 0, 1, 5, 11, 6, -1, -1, -1, -1, -1,
          -1, -1, -1, -1, 1, 8, 3, 1, 9, 8, 5, 11, 6, -1, -1, -1, -1, -1, -1,
          1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, 6, 5, 1, 2,
          6, 3, 0, 8, -1, -1, -1, -1, -1, -1, 9, 6, 5, 9, 0, 6, 0, 2, 6, -1,
          -1, -1, -1, -1, -1, 5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1,
          2, 3, 10, 11, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10, 0, 8, 10,
          2, 0, 11, 6, 5, -1, -1, -1, -1, -1, -1, 0, 1, 9, 2, 3, 10, 5, 11, 6,
          -1, -1, -1, -1, -1, -1, 5, 11, 6, 1, 9, 2, 9, 10, 2, 9, 8, 10, -1,
          -1, -1, 6, 3, 10, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, 0, 8, 10,
          0, 10, 5, 0, 5, 1, 5, 10, 6, -1, -1, -1, 3, 10, 6, 0, 3, 6, 0, 6, 5,
          0, 5, 9, -1, -1, -1, 6, 5, 9, 6, 9, 10, 10, 9, 8, -1, -1, -1, -1, -1,
          -1, 5, 11, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 3, 0,
          4, 7, 3, 6, 5, 11, -1, -1, -1, -1, -1, -1, 1, 9, 0, 5, 11, 6, 8, 4,
          7, -1, -1, -1, -1, -1, -1, 11, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1,
          -1, -1, 6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, 1, 2, 5,
          5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, 8, 4, 7, 9, 0, 5, 0, 6, 5, 0,
          2, 6, -1, -1, -1, 7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, 3, 10,
          2, 7, 8, 4, 11, 6, 5, -1, -1, -1, -1, -1, -1, 5, 11, 6, 4, 7, 2, 4,
          2, 0, 2, 7, 10, -1, -1, -1, 0, 1, 9, 4, 7, 8, 2, 3, 10, 5, 11, 6, -1,
          -1, -1, 9, 2, 1, 9, 10, 2, 9, 4, 10, 7, 10, 4, 5, 11, 6, 8, 4, 7, 3,
          10, 5, 3, 5, 1, 5, 10, 6, -1, -1, -1, 5, 1, 10, 5, 10, 6, 1, 0, 10,
          7, 10, 4, 0, 4, 10, 0, 5, 9, 0, 6, 5, 0, 3, 6, 10, 6, 3, 8, 4, 7, 6,
          5, 9, 6, 9, 10, 4, 7, 9, 7, 10, 9, -1, -1, -1, 11, 4, 9, 6, 4, 11,
          -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 11, 6, 4, 9, 11, 0, 8, 3, -1,
          -1, -1, -1, -1, -1, 11, 0, 1, 11, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1,
          -1, 8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 11, -1, -1, -1, 1, 4, 9, 1, 2,
          4, 2, 6, 4, -1, -1, -1, -1, -1, -1, 3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6,
          4, -1, -1, -1, 0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1,
          8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, 11, 4, 9, 11, 6,
          4, 10, 2, 3, -1, -1, -1, -1, -1, -1, 0, 8, 2, 2, 8, 10, 4, 9, 11, 4,
          11, 6, -1, -1, -1, 3, 10, 2, 0, 1, 6, 0, 6, 4, 6, 1, 11, -1, -1, -1,
          6, 4, 1, 6, 1, 11, 4, 8, 1, 2, 1, 10, 8, 10, 1, 9, 6, 4, 9, 3, 6, 9,
          1, 3, 10, 6, 3, -1, -1, -1, 8, 10, 1, 8, 1, 0, 10, 6, 1, 9, 1, 4, 6,
          4, 1, 3, 10, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, 6, 4, 8,
          10, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, 7, 11, 6, 7, 8, 11, 8,
          9, 11, -1, -1, -1, -1, -1, -1, 0, 7, 3, 0, 11, 7, 0, 9, 11, 6, 7, 11,
          -1, -1, -1, 11, 6, 7, 1, 11, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, 11, 6,
          7, 11, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, 1, 2, 6, 1, 6, 8, 1, 8,
          9, 8, 6, 7, -1, -1, -1, 2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9,
          7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, 7, 3, 2, 6, 7, 2,
          -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 3, 10, 11, 6, 8, 11, 8, 9, 8,
          6, 7, -1, -1, -1, 2, 0, 7, 2, 7, 10, 0, 9, 7, 6, 7, 11, 9, 11, 7, 1,
          8, 0, 1, 7, 8, 1, 11, 7, 6, 7, 11, 2, 3, 10, 10, 2, 1, 10, 1, 7, 11,
          6, 1, 6, 7, 1, -1, -1, -1, 8, 9, 6, 8, 6, 7, 9, 1, 6, 10, 6, 3, 1, 3,
          6, 0, 9, 1, 10, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, 7, 8, 0, 7,
          0, 6, 3, 10, 0, 10, 6, 0, -1, -1, -1, 7, 10, 6, -1, -1, -1, -1, -1,
          -1, -1, -1, -1, -1, -1, -1, 7, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1,
          -1, -1, -1, -1, 3, 0, 8, 10, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1,
          -1, 0, 1, 9, 10, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, 1, 9,
          8, 3, 1, 10, 7, 6, -1, -1, -1, -1, -1, -1, 11, 1, 2, 6, 10, 7, -1,
          -1, -1, -1, -1, -1, -1, -1, -1, 1, 2, 11, 3, 0, 8, 6, 10, 7, -1, -1,
          -1, -1, -1, -1, 2, 9, 0, 2, 11, 9, 6, 10, 7, -1, -1, -1, -1, -1, -1,
          6, 10, 7, 2, 11, 3, 11, 8, 3, 11, 9, 8, -1, -1, -1, 7, 2, 3, 6, 2, 7,
          -1, -1, -1, -1, -1, -1, -1, -1, -1, 7, 0, 8, 7, 6, 0, 6, 2, 0, -1,
          -1, -1, -1, -1, -1, 2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1,
          -1, 1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, 11, 7, 6, 11, 1,
          7, 1, 3, 7, -1, -1, -1, -1, -1, -1, 11, 7, 6, 1, 7, 11, 1, 8, 7, 1,
          0, 8, -1, -1, -1, 0, 3, 7, 0, 7, 11, 0, 11, 9, 6, 11, 7, -1, -1, -1,
          7, 6, 11, 7, 11, 8, 8, 11, 9, -1, -1, -1, -1, -1, -1, 6, 8, 4, 10, 8,
          6, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 6, 10, 3, 0, 6, 0, 4, 6,
          -1, -1, -1, -1, -1, -1, 8, 6, 10, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1,
          -1, -1, 9, 4, 6, 9, 6, 3, 9, 3, 1, 10, 3, 6, -1, -1, -1, 6, 8, 4, 6,
          10, 8, 2, 11, 1, -1, -1, -1, -1, -1, -1, 1, 2, 11, 3, 0, 10, 0, 6,
          10, 0, 4, 6, -1, -1, -1, 4, 10, 8, 4, 6, 10, 0, 2, 9, 2, 11, 9, -1,
          -1, -1, 11, 9, 3, 11, 3, 2, 9, 4, 3, 10, 3, 6, 4, 6, 3, 8, 2, 3, 8,
          4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, 0, 4, 2, 4, 6, 2, -1, -1, -1,
          -1, -1, -1, -1, -1, -1, 1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1,
          -1, 1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, 8, 1, 3, 8, 6,
          1, 8, 4, 6, 6, 11, 1, -1, -1, -1, 11, 1, 0, 11, 0, 6, 6, 0, 4, -1,
          -1, -1, -1, -1, -1, 4, 6, 3, 4, 3, 8, 6, 11, 3, 0, 3, 9, 11, 9, 3,
          11, 9, 4, 6, 11, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 9, 5, 7,
          6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8, 3, 4, 9, 5, 10, 7,
          6, -1, -1, -1, -1, -1, -1, 5, 0, 1, 5, 4, 0, 7, 6, 10, -1, -1, -1,
          -1, -1, -1, 10, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, 9, 5, 4,
          11, 1, 2, 7, 6, 10, -1, -1, -1, -1, -1, -1, 6, 10, 7, 1, 2, 11, 0, 8,
          3, 4, 9, 5, -1, -1, -1, 7, 6, 10, 5, 4, 11, 4, 2, 11, 4, 0, 2, -1,
          -1, -1, 3, 4, 8, 3, 5, 4, 3, 2, 5, 11, 5, 2, 10, 7, 6, 7, 2, 3, 7, 6,
          2, 5, 4, 9, -1, -1, -1, -1, -1, -1, 9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8,
          7, -1, -1, -1, 3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, 6, 2,
          8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, 9, 5, 4, 11, 1, 6, 1, 7, 6, 1,
          3, 7, -1, -1, -1, 1, 6, 11, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, 4, 0,
          11, 4, 11, 5, 0, 3, 11, 6, 11, 7, 3, 7, 11, 7, 6, 11, 7, 11, 8, 5, 4,
          11, 4, 8, 11, -1, -1, -1, 6, 9, 5, 6, 10, 9, 10, 8, 9, -1, -1, -1,
          -1, -1, -1, 3, 6, 10, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, 0, 10,
          8, 0, 5, 10, 0, 1, 5, 5, 6, 10, -1, -1, -1, 6, 10, 3, 6, 3, 5, 5, 3,
          1, -1, -1, -1, -1, -1, -1, 1, 2, 11, 9, 5, 10, 9, 10, 8, 10, 5, 6,
          -1, -1, -1, 0, 10, 3, 0, 6, 10, 0, 9, 6, 5, 6, 9, 1, 2, 11, 10, 8, 5,
          10, 5, 6, 8, 0, 5, 11, 5, 2, 0, 2, 5, 6, 10, 3, 6, 3, 5, 2, 11, 3,
          11, 5, 3, -1, -1, -1, 5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1,
          9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, 1, 5, 8, 1, 8, 0,
          5, 6, 8, 3, 8, 2, 6, 2, 8, 1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1,
          -1, -1, -1, 1, 3, 6, 1, 6, 11, 3, 8, 6, 5, 6, 9, 8, 9, 6, 11, 1, 0,
          11, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, 0, 3, 8, 5, 6, 11, -1, -1,
          -1, -1, -1, -1, -1, -1, -1, 11, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1,
          -1, -1, -1, -1, 10, 5, 11, 7, 5, 10, -1, -1, -1, -1, -1, -1, -1, -1,
          -1, 10, 5, 11, 10, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, 5, 10, 7,
          5, 11, 10, 1, 9, 0, -1, -1, -1, -1, -1, -1, 11, 7, 5, 11, 10, 7, 9,
          8, 1, 8, 3, 1, -1, -1, -1, 10, 1, 2, 10, 7, 1, 7, 5, 1, -1, -1, -1,
          -1, -1, -1, 0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 10, -1, -1, -1, 9, 7, 5,
          9, 2, 7, 9, 0, 2, 2, 10, 7, -1, -1, -1, 7, 5, 2, 7, 2, 10, 5, 9, 2,
          3, 2, 8, 9, 8, 2, 2, 5, 11, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1,
          8, 2, 0, 8, 5, 2, 8, 7, 5, 11, 2, 5, -1, -1, -1, 9, 0, 1, 5, 11, 3,
          5, 3, 7, 3, 11, 2, -1, -1, -1, 9, 8, 2, 9, 2, 1, 8, 7, 2, 11, 2, 5,
          7, 5, 2, 1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, 8,
          7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, 9, 0, 3, 9, 3, 5, 5, 3,
          7, -1, -1, -1, -1, -1, -1, 9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1,
          -1, -1, -1, 5, 8, 4, 5, 11, 8, 11, 10, 8, -1, -1, -1, -1, -1, -1, 5,
          0, 4, 5, 10, 0, 5, 11, 10, 10, 3, 0, -1, -1, -1, 0, 1, 9, 8, 4, 11,
          8, 11, 10, 11, 4, 5, -1, -1, -1, 11, 10, 4, 11, 4, 5, 10, 3, 4, 9, 4,
          1, 3, 1, 4, 2, 5, 1, 2, 8, 5, 2, 10, 8, 4, 5, 8, -1, -1, -1, 0, 4,
          10, 0, 10, 3, 4, 5, 10, 2, 10, 1, 5, 1, 10, 0, 2, 5, 0, 5, 9, 2, 10,
          5, 4, 5, 8, 10, 8, 5, 9, 4, 5, 2, 10, 3, -1, -1, -1, -1, -1, -1, -1,
          -1, -1, 2, 5, 11, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, 5, 11, 2, 5,
          2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, 3, 11, 2, 3, 5, 11, 3, 8, 5,
          4, 5, 8, 0, 1, 9, 5, 11, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, 8,
          4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, 0, 4, 5, 1, 0, 5, -1,
          -1, -1, -1, -1, -1, -1, -1, -1, 8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5,
          -1, -1, -1, 9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
          4, 10, 7, 4, 9, 10, 9, 11, 10, -1, -1, -1, -1, -1, -1, 0, 8, 3, 4, 9,
          7, 9, 10, 7, 9, 11, 10, -1, -1, -1, 1, 11, 10, 1, 10, 4, 1, 4, 0, 7,
          4, 10, -1, -1, -1, 3, 1, 4, 3, 4, 8, 1, 11, 4, 7, 4, 10, 11, 10, 4,
          4, 10, 7, 9, 10, 4, 9, 2, 10, 9, 1, 2, -1, -1, -1, 9, 7, 4, 9, 10, 7,
          9, 1, 10, 2, 10, 1, 0, 8, 3, 10, 7, 4, 10, 4, 2, 2, 4, 0, -1, -1, -1,
          -1, -1, -1, 10, 7, 4, 10, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, 2, 9,
          11, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, 9, 11, 7, 9, 7, 4, 11, 2,
          7, 8, 7, 0, 2, 0, 7, 3, 7, 11, 3, 11, 2, 7, 4, 11, 1, 11, 0, 4, 0,
          11, 1, 11, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, 9, 1,
          4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, 4, 9, 1, 4, 1, 7, 0, 8, 1,
          8, 7, 1, -1, -1, -1, 4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1,
          -1, -1, 4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9,
          11, 8, 11, 10, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 0, 9, 3, 9,
          10, 10, 9, 11, -1, -1, -1, -1, -1, -1, 0, 1, 11, 0, 11, 8, 8, 11, 10,
          -1, -1, -1, -1, -1, -1, 3, 1, 11, 10, 3, 11, -1, -1, -1, -1, -1, -1,
          -1, -1, -1, 1, 2, 10, 1, 10, 9, 9, 10, 8, -1, -1, -1, -1, -1, -1, 3,
          0, 9, 3, 9, 10, 1, 2, 9, 2, 10, 9, -1, -1, -1, 0, 2, 10, 8, 0, 10,
          -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, 2, 10, -1, -1, -1, -1, -1, -1,
          -1, -1, -1, -1, -1, -1, 2, 3, 8, 2, 8, 11, 11, 8, 9, -1, -1, -1, -1,
          -1, -1, 9, 11, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, 3,
          8, 2, 8, 11, 0, 1, 8, 1, 11, 8, -1, -1, -1, 1, 11, 2, -1, -1, -1, -1,
          -1, -1, -1, -1, -1, -1, -1, -1, 1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1,
          -1, -1, -1, -1, 0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
          -1, 0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
          -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
}
